package tree;

import java.util.ArrayDeque;

public class BinarySortTree {

    public static void main(String[] args) {
        BinarySortTree sortTree = new BinarySortTree();
        sortTree.add(new BinarySortTreeNode(62), null);
        sortTree.add(new BinarySortTreeNode(88), null);
        sortTree.add(new BinarySortTreeNode(58), null);
        sortTree.add(new BinarySortTreeNode(47), null);
        sortTree.add(new BinarySortTreeNode(35), null);
        sortTree.add(new BinarySortTreeNode(73), null);
        sortTree.add(new BinarySortTreeNode(51), null);
        sortTree.add(new BinarySortTreeNode(99), null);
        sortTree.add(new BinarySortTreeNode(37), null);
        sortTree.add(new BinarySortTreeNode(93), null);
        sortTree.add(new BinarySortTreeNode(29), null);
        sortTree.add(new BinarySortTreeNode(36), null);
        sortTree.add(new BinarySortTreeNode(49), null);
        sortTree.add(new BinarySortTreeNode(48), null);
        sortTree.add(new BinarySortTreeNode(50), null);
        sortTree.add(new BinarySortTreeNode(56), null);
        sortTree.sout(sortTree.head);
        System.out.println("================");
        sortTree.deleteNode(93);
        sortTree.sout(sortTree.head);
        System.out.println("================");
    }

    void sout(BinarySortTreeNode head) {
        if (head == null) {
            return;
        }

        sout(head.Left);
        System.out.println(head.data);
        sout(head.right);
    }

    public BinarySortTreeNode head;

    void add(BinarySortTreeNode node, BinarySortTreeNode parent) {
        if (head == null) {
            head = node;
            return;
        }
        if (parent == null) {
            parent = head;
        }
        if (parent.data >= node.data) {
            if (parent.Left == null) {
                parent.Left = node;
            } else {
                add(node, parent.Left);
            }
        } else {
            if (parent.right == null) {
                parent.right = node;
            } else {
                add(node, parent.right);
            }
        }
    }

    BinarySortTreeNode find(int target) {
        ArrayDeque<BinarySortTreeNode> deque = new ArrayDeque<>();
        if (head.data == target) {
            return head;
        } else {
            if (head.right != null) {
                deque.push(head.right);
            }
            if (head.Left != null) {
                deque.push(head.Left);
            }
            while (!deque.isEmpty()) {
                BinarySortTreeNode treeNode = deque.pop();
                if (treeNode.data == target) {
                    return treeNode;
                }
                if (treeNode.right != null) {
                    deque.push(treeNode.right);
                }
                if (treeNode.Left != null) {
                    deque.push(treeNode.Left);
                }
            }
            return  null;
        }
    }

    void deleteNode(int target) {
        BinarySortTreeNode targetNode = find(target);
        if (targetNode.Left == null && targetNode.right == null) {

        } else if (targetNode.Left == null) {
            targetNode.data = targetNode.right.data;
            targetNode.right = null;
        } else if (targetNode.right == null) {
            targetNode.data = targetNode.right.data;
            targetNode.Left = null;
        } else {
            BinarySortTreeNode node = targetNode.Left;
            BinarySortTreeNode parent = null;
            while (node.right!=null){
                parent = node;
                node = node.right;
            }
            targetNode.data = node.data;
            if (node.Left == null){
                parent.right = null;
            }else {
                node.data = node.Left.data;
                node.Left = null;
            }
        }
    }


}

class BinarySortTreeNode {

    public BinarySortTreeNode Left;

    public BinarySortTreeNode right;

    public int data;

    public BinarySortTreeNode() {
    }

    public BinarySortTreeNode(int data) {
        this.data = data;
    }
}

